Discrete optimization is an important branch of applied mathematics. The importance of discrete optimization relies in the vast number of real-world applications that can be formulated as a discrete optimization problem, for example, vehicle routing problem, traveling salesman problem, planning and scheduling, etc.
The solution to a hard discrete optimization problem can be encoded in the ground state of a K-spin problem, also known as a pseudo-Boolean model. Hence, any optimization solver able to find the ground state, i.e., the low-energy state, of a K-spin problem can be used to find the solution to the discrete optimization problem.
Examples of such optimization solvers are the quantum annealer device commercialized by D-Wave Systems (see Johnson, M W et al., “Quantum annealing with manufactured spins,” Nature 473.7346 (2011): 194-198), and the Hamze-de Freitas-Selby algorithm (HFS) (see Selby, Alex, “Efficient subgraph-based sampling of Ising-type models with frustration,” arXiv preprint arXiv:1409.3934 (2014)). (See also Hamze, Firas, and Nando de Freitas, “From fields to trees,” Proceedings of the 20th conference on uncertainty in artificial intelligence 7 Jul. 2004: 243-250), which are computational approaches for finding the low-energy state of a 2-spin problem.
Unfortunately, implementing a practical discrete optimization problem is very challenging due to various limitations of the optimization solver used.
For example, one of the main limitations of the D-Wave device is the sparse connectivity of its hardware graph. Specifically, the D-Wave device consists of a hardware graph where each vertex is a physical qubit and each edge is a physical coupler between two qubits.
In the case of the Hamze-de Freitas-Selby optimization solver, there is also a limitation in terms of the connectivity of its variables.
It will therefore be appreciated by the skilled addressee that a discrete optimization problem may require a different connectivity than the one defined by the solver graph. In such case, a mapping from the discrete optimization problem graph to the solver graph is required.
In one embodiment, where the optimization solver is a 2-spin solver, this mapping is commonly achieved by using Minor Embedding (ME) techniques. It is worth mentioning that if the optimization solver is a K-spin solver with K>2, it has been assumed that the optimization solver's variables can be arranged such that a Minor Embedding approach is still needed. An example of such arrangement is a hypergraph where the edges, also known as hyperedges, can connect up to and including K vertices, but it is not fully connected.
In a Minor Embedding approach, a graph G representing an optimization problem is replaced by a subgraph Gemb of the solver graph where each of graph G's vertices is replaced by a connected subgraph of the optimization solver graph.
After an embedding representation is found, the next step is to determine the corresponding parameters of the embedded problem. This problem is referred to as the parameter setting problem. The skilled addressee will appreciate that the reduction of an optimization problem to its minor embedding form is correct as long as there is a one-to-one correspondence between the ground states of both representations G and Gemb.
Various algorithms have been disclosed to find a minor embedding.
For instance, an example of an algorithm is disclosed by Cai et al. (see Cai, Jun, William G Macready, and Aidan Roy, “A practical heuristic for finding graph minors,” arXiv preprint arXiv:1406.2741 (2014)).
A method for performing a parameter setting has been disclosed by Choi (See Choi, Vicky, “Minor-embedding in adiabatic quantum computation: I. The parameter setting problem,” Quantum Information Processing 7.5 (2008): 193-209). In the approach disclosed by Choi, the parameter setting problem is defined for a 2-spin problem on a specific quantum annealer, i.e., the D-Wave device.
Specifically, Choi addressed the parameter setting problem by considering that the connected subgraphs representing variables in graph G are subtrees of the hardware graph. Unfortunately, this condition does not necessarily hold for all embedded problems. This is, therefore, a serious limitation.
Other disadvantages of the prior-art methods are that they require more computational resources and are limited to 2-spin solvers.
There is a need for a method and system that will overcome at least one of the above-identified drawbacks.
Features of the invention will be apparent from review of the disclosure, drawings and description of the invention below.